import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Solution {
    /**
     * @param points: a list of points
     * @param origin: a point
     * @param k: An integer
     * @return: the k closest points
     */
    public Point[] kClosest(Point[] points, Point origin, int k) {



        /*******************************希尔排序测试*****************************/
        /*
        int len = 8000;
        int num1 = 0;
        int num2 = 0;
        for(int h = 0;h < 70;h += 1){
            int[] arr = new int[len];
            int[] arr1 = new int[len];
            Random r = new Random();
            for(int i = 0;i<len;i+=1){
                arr[i] = r.nextInt(50000);
                arr1[i] = arr[i];
            }
            //System.out.print(Arrays.toString(arr));
            long t1 = System.currentTimeMillis();
            shellSort2(arr);
            long t2 = System.currentTimeMillis();
            shellSort2(arr1);
            long t3 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
            //System.out.println((t3 - t2) + "ms_" + (t4 - t3));
        }
        System.out.println(Integer.MAX_VALUE>>29);
        System.out.println(num1+ "ms_" + num2);
        */
        /*******************************希尔排序测试*****************************/
        /*******************************找最大值最小值测试*****************************/
        /*
        int len = 8000000;
        int[] arr = new int[len];
        Random r = new Random();
        for(int i = 0;i<len;i+=1){
            arr[i] = r.nextInt(500000);
        }
        long t1 = System.currentTimeMillis();
        System.out.println(getMaxDigit(arr));
        long t2 = System.currentTimeMillis();
        long t3 = System.currentTimeMillis();
        System.out.println((t2 - t1) + "\t" + (t3 - t2));
        */
        /*******************************找最大值最小值测试*****************************/
        /*******************************基数排序测试*****************************/
        /*
        //基数排序分析
        //1. 设定一个基数，例如10（不一定非要是10），准备10个数组（为了节省空间，这里使用十个ArrayLIst）
        int baseNum = 10;
        //ArrayList[]<Integer> bks = new ArrayList[baseNum]<Integer>;
        List<ArrayList<Integer>> bks = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < baseNum; i += 1){//创建baseNum个桶，这里为10
            ArrayList<Integer> nal = new ArrayList<Integer>();
            bks.add(nal);
            //bks[i] = nal;
        }

        int len = 80000;
        int[] arr = new int[len];
        Random r = new Random();
        for(int i = 0;i<len;i+=1){
            arr[i] = r.nextInt(500000);
        }


        //System.out.println(Arrays.toString(arr));
        long t1 = System.currentTimeMillis();
        distributionSort(arr, baseNum, bks);
        long t2 = System.currentTimeMillis();

        System.out.println((t2 - t1));
        System.out.println(Arrays.toString(arr));
        */
        /*******************************基数排序测试*****************************/
        //获取一个数的倒数第n位数，获取不到则为0
        /*
        int baseNum = 10;
        //ArrayList[]<Integer> bks = new ArrayList[baseNum]<Integer>;
        List<ArrayList<Integer>> bks = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < baseNum; i += 1){//创建baseNum个桶，这里为10
            ArrayList<Integer> nal = new ArrayList<Integer>();
            bks.add(nal);
            //bks[i] = nal;
        }
        int len = 8000;
        int num1 = 0;
        int num2 = 0;
        for(int h = 0;h < 1;h += 1){
            int[] arr = new int[len];
            int[] arr1 = new int[len];
            Random r = new Random();
            for(int i = 0;i<len;i+=1){
                arr[i] = r.nextInt(5000);
                arr1[i] = arr[i];
            }
            //System.out.print(Arrays.toString(arr));
            long t1 = System.currentTimeMillis();
            shellSort(arr);
            long t2 = System.currentTimeMillis();
            distributionSort(arr, 10, bks);
            long t3 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
            //System.out.println((t3 - t2) + "ms_" + (t4 - t3));
        }
        System.out.println(num1+ "\t" + num2);
        */


        /*int num = 542348;
        int baseNum = 10;
        for(int i = 0; i < getNumLenght(num)+2; i += 1){
            int temp = (int)Math.pow(baseNum, i);
            System.out.println(num % (temp*baseNum) / temp);
        }*/
        /*************************************基数与希尔的比较*************************************/
        return null;
    }

}

